package stack;

import java.util.Arrays;

/**
 * leet-code(739) 每日温度
 *
 * @author Ringo
 * @date 2022/2/4 23:31
 */
public class DailyTemperatures {


    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println(Arrays.toString(dailyTemperatures(temperatures)));
    }

    /**
     * temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
     * 0   1   2   3   4   5   6   7
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        final int length = temperatures.length;
        int p = -1;
        int[] stack = new int[length], result = new int[length];
        for (int i = 0; i < length; ++i) {
            while (p > -1 && temperatures[i] > temperatures[stack[p]]) {
                int index = stack[p--];
                result[index] = i - index;
            }
            stack[++p] = i;
        }
        return result;
    }

    private static void monotoneStackDemo(int[] arr) {
        final int length = arr.length;
        int p = -1;
        int[] stack = new int[length];
        for (int i = 0; i < length; ++i) {
            while (p > -1 && arr[stack[p]] > arr[i]) --p;
            stack[++p] = i;
        }
        System.out.println("栈内元素: ");
        for (int i = 0; i <= p; ++i) {
            System.out.print(stack[i] + ", ");
        }
    }
}
